package Example_practice02;

import com.sun.java.swing.plaf.windows.WindowsTabbedPaneUI;
import examination_practice01.MaxSonArray;

public class MulMaxSun {
    //动态规划实现最大子段和
    public static int DPMaxArray(int[] arr){
        int n=arr.length;
        int[] dp=new int[n+1];
        int Sum=Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            dp[i]=Math.max(arr[i-1],dp[i-1]+dp[i-1]);
            Sum =Math.max(dp[i],Sum);
        }
        return Sum;
    }
    //暴力算法求解最大子段和
    public static int BFMaxArray(int[] arr){
        int Sum=0;
        int n=arr.length;
        for (int i=0;i<n;i++){
            for (int j=0;j<=i;j++){
                int curSum=0;
                for (int k=0;k<=j;k++){
                    curSum+=arr[k];
                }
                if (curSum>Sum){
                    Sum=curSum;
                }
            }
        }
        return Sum;
    }
    //分治法求最大子段和
    public static int DCMaxArray(int[] arr){
        return divideAndConquer(arr,0,arr.length-1);
    }
    private static  int divideAndConquer(int[] arr,int start,int end){
        //如果数组只有一个元素
        if (start==end){
            return arr[start]>0?arr[start]:0;
        }

        int mid=(start+end)/2;
        //递归求解左半部分最大子数组和
        int leftMax=divideAndConquer(arr,start,mid);
        //递归求解右半部分最大子数组和
        int rightMax=divideAndConquer(arr,mid+1,end);

        //计算跨中间位置的最大子数组和
        int crossMax=findCrossMax(arr,start,end,mid);

        return Math.max(Math.max(leftMax,rightMax),crossMax);
    }

    private static int findCrossMax(int[] arr,int start,int end,int mid){
        int leftMax=Integer.MIN_VALUE;
        int sum=0;
        for (int i=mid;i>=start;i--){
            sum+=arr[i];
            leftMax=Math.max(sum,leftMax);
        }

        int rightMax=Integer.MIN_VALUE;
        sum=0;
        for (int i=mid+1;i<=end;i++){
            sum+=arr[i];
            rightMax=Math.max(sum,rightMax);
        }
        return rightMax+leftMax;
    }
}

